package code735;

import java.util.Arrays;
import java.util.Stack;

public class Code735 {
    static class Solution {
        /**
         * 使用栈解决行星碰撞问题
         * @param asteroids 星星数组
         * @return 碰撞后的星星数组
         */
        public int[] asteroidCollision(int[] asteroids) {
            Stack<Integer> stack = new Stack<>();
            for (int asteroid : asteroids) {
                if (stack.isEmpty()) {
                    stack.add(asteroid);
                }else {
                    while (true) {
                        int temp =  stack.pop();
                        if (temp >= 0 && asteroid < 0) {//栈顶星星向右，将要入站得星星向左
                            if (temp > Math.abs(asteroid)) { //栈顶的星星比要入站的星星大
                                stack.push(temp);
                                break;
                            } else if (temp < Math.abs(asteroid)) {//栈顶的星星比要入栈的星星小
                                if (stack.isEmpty()){
                                    stack.push(asteroid);
                                    break;
                                }
                            } else {//二者一样大，泯灭
                                break;
                            }
                        } else {
                            stack.push(temp);
                            stack.push(asteroid);
                            break;
                        }
                    }
                }
            }
            int[] arr = new int[stack.size()];
            for (int j = 0; j < arr.length; j++) {
                arr[arr.length-j-1] = stack.pop();
            }
            return arr;
        }


    }
    public static void main(String[] args) {
        int[] asteroids = new int[]{1,-2,-2,-2};
        System.out.println(Arrays.toString(new Code735.Solution().asteroidCollision(asteroids)));
    }
}
